'''
Created on Feb 14, 2010

@author: Roni
'''
from cliques.potentialBasedSearch import potentialBasedSearch
import random


class ClosestCliqueSearch(potentialBasedSearch):
    '''
    classdocs
    '''
    MAX_VALUE = 1000000
    
    
    def __init__(self):
        '''
        Constructor
        '''
        potentialBasedSearch.__init__(self)
        self.g = dict()
        self.parent = dict()

    def generate(self, parent, new_node):
        ''' Update parent and g if necessary '''
        potentialBasedSearch.generate(self, parent, new_node)
        if self.g.has_key(new_node):
            if self.g[new_node]>self.g[parent]:
                self.parent[new_node]=parent
                self.g[new_node]=self.g[parent]+1
        else:
            if parent == None:
                self.parent[new_node]=None
                self.g[new_node]=0                
            else:
                self.parent[new_node]=parent
                self.g[new_node]=self.g[parent]+1        


    def setup(self, unknown_graph, k, start_node):
        self.g.clear()
        self.parent.clear()
        self.generated=[]
        
        self.parent[start_node]=None
        self.g[start_node]=0                  
        potentialBasedSearch.setup(self, unknown_graph, k, start_node)
        

    def expand(self, node):
        # Update CKG, expanded, generated, g and parent
        potentialBasedSearch.expand(self,node)      
        self.update_g(node)
 
    
 
    def update_g(self,node):
        ''' Update the g-value of the generated nodes '''
        g_node = self.g[node]
        for neighbor in self.unknown_graph.neighbors(node):
            if self.g.has_key(neighbor):
                if self.g[neighbor]>g_node:
                    self.parent[neighbor]=node
                    self.g[neighbor]=g_node+1
            else:
                self.parent[neighbor]=node
                self.g[neighbor]=g_node+1
        
    def choose_node(self):
        ''' Choose a node to explore '''
        ties = []
        min_node=None
        min_value = ClosestCliqueSearch.MAX_VALUE
        min_value_g = -1
        for node in self.generated:
            value = self.calculate_node_value(node)
            if value<min_value:
                ties=[]
                min_value = value
                min_node = node
                min_value_g = self.g[node]
            else:
                if value==min_value: 
                    if min_value_g<self.g[node]: # Tie-brake in favor of larger g-values
                        min_value_g = self.g[node]
                        ties.append(min_node) # Store for possible future tie braking
                        min_node = node
                    else:
                        ties.append(node) # Store for possible future tie braking
        return min_node 

    def calculate_node_value(self,node):
        ''' Return the cost function for this node '''
        max_core = 0
        max_kPc = None
        if self.generated_to_kPc.has_key(node):
            for kPc in self.generated_to_kPc[node]:
                if len(kPc.core)>max_core:
                    max_core = len(kPc.core)
                    max_kPc=kPc

        return self.g[node]+self.k-1-max_core
            
        
    def __str__(self):
        return "Closest-Clique*"
        